package com.leetcode;

/**
 * 64. 最小路径和
 *
 * @author fy
 * @date 2022/3/28 21:10
 */
public class Solution64 {

    private int m, n;
    private int[][] sum;
    /**
     * 64. 最小路径和
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        sum = new int[this.m][this.n];
        for (int i = 0; i < this.m; i++) {
            for (int j = 0; j < this.n; j++) {
                sum[i][j] = -1;
            }
        }
        return sum(grid, m - 1, n - 1);
    }

    public int sum(int[][] grid, int x, int y) {
        if (sum[x][y] != -1L) {
            return sum[x][y];
        }
        if (x == 0 && y == 0) {
            return grid[x][y];
        }
        int oldX = x - 1;
        int tmp = Integer.MAX_VALUE;
        if (oldX >= 0) {
            tmp = Math.min(sum(grid, oldX, y) + grid[x][y], tmp);
        }
        int newY = y - 1;
        if (newY >= 0) {
            tmp = Math.min(sum(grid, x, newY) + grid[x][y], tmp);
        }
        sum[x][y] = tmp;
        return tmp;
    }

    public int minPathSum1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 1; i < n; i++) {
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }

        for (int j = 1; j < m; j++) {
            grid[j][0] = grid[j - 1][0] + grid[j][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[m - 1][n - 1];
    }

}
